427D - Match Catch - CodeForces Solution

#include<bits/stdc++.h>
#define int long long
using namespace std;

int read() {
	char ch=getchar();
	int f=1,x=0;
	while(ch<'0'||ch>'9') {
		if(ch=='-')
			f=-1;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9') {
		x=x*10+ch-'0';
		ch=getchar();
	}
	return f*x;
}

const int MAXN=2e5+10; 

int n,m;
int sa[MAXN],rnk[MAXN],height[MAXN],tmp[MAXN],a[MAXN],b[MAXN],cnt[MAXN],calc[MAXN],bel[MAXN];
char s[MAXN];

void bucket_sort(int v[]) {
	fill(cnt,cnt+m+1,0);
	for(int i=1;i<=n;i++) {
		cnt[v[i]+1]++;
	}
	for(int i=1;i<=m;i++) {
		cnt[i]+=cnt[i-1];
	}
	for(int i=1;i<=n;i++) {
		tmp[++cnt[v[sa[i]]]]=sa[i];
	}
	for(int i=1;i<=n;i++) {
		sa[i]=tmp[i];
	}
}

void get_sa() {
	for(int i=1;i<=n;i++) {
		rnk[i]=tmp[i]=s[i];
		sa[i]=i;
	}
	sort(tmp+1,tmp+n+1);
	m=unique(tmp+1,tmp+n+1)-tmp-1;
	for(int i=1;i<=n;i++) {
		rnk[i]=lower_bound(tmp+1,tmp+m+1,rnk[i])-tmp;
	}
	
	for(int l=1;l<n;l<<=1) {
		for(int i=1;i<=n;i++) {
			a[i]=rnk[i];
			b[i]=(i+l<=n? rnk[i+l]:0);
		}
		bucket_sort(b);
		bucket_sort(a);
		
		m=0;
		for(int i=1;i<=n;i++) {
			if(a[sa[i]]!=a[sa[i-1]]||b[sa[i]]!=b[sa[i-1]]) {
				m++;
			}
			rnk[sa[i]]=m;
		}
	}
}

void get_height() {
	int h=0;
	for(int i=1;i<=n;i++) {
		if(h) {
			h--;
		}
		if(rnk[i]==1) {
			continue;
		}
		
		int p=i+h;
		int q=sa[rnk[i]-1]+h;
		
		while(p<=n&&q<=n&&s[p]==s[q]) {
			p++;
			q++;
			h++;
		}
		height[rnk[i]]=h;
	}
}

int solve() {
	int ans=1e9+10;
	bool flag=0;
	
	for(int i=2;i<=n;i++) {
		if(height[i]>height[i-1]&&height[i]>height[i+1]) {
			if(bel[sa[i]]!=bel[sa[i-1]]) {
				ans=min(max(height[i-1],height[i+1])+1,ans);
				flag=1;
			}
		}
	}
	
	return flag? ans:-1;
}

signed main() {
	scanf("%s",s+1);
	n=strlen(s+1);
	for(int i=1;i<=n;i++) {
		bel[i]=1;
	}
	s[n+1]='$';
	scanf("%s",s+n+2);
	n=strlen(s+1);
	for(int i=1;i<=n;i++) {
		if(!bel[i]&&s[i]!='$') {
			bel[i]=2;
		}
	}
		
	get_sa();
	get_height();
	
	printf("%lld\n",solve());
	return 0;
}